package com.example.algorithm.sorts;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] nums = {3,5,7,4,2,9,1,3};
        int[] sorted = mergeSort(nums);

        for (int num : sorted) {
            System.out.print(num + ",");
        }
    }

    /**
     * 分治思想（递归）
     * 递：先将数组分成两部分，直到每个子数组只有一个元素时，不再进行划分
     * 归：然后依次将两个子数组合并成一个有序的数组，直到所有数组都合并完毕
     * @param nums
     */
    private static int[] mergeSort(int[] nums) {
        if (nums.length < 2)
            return nums;

        int mid = nums.length / 2;

        // 递归将数组切成两块(left, right)
        int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));

        // 合并左右两个子数组
        return merge(left, right);

    }

    private static int[] merge(int[] left, int[] right) {
        int[] mergedArr = new int[left.length + right.length];

        int leftIndex = 0,rightIndex = 0;
        for (int i = 0; i < mergedArr.length; i++) {
            // 左右子数组都还有元素未被放入到合并的数组中
            // 此时取两个子数组指针指向的元素的最小值放入mergedArr
            if ((leftIndex < left.length) && (rightIndex < right.length)) {
                if (left[leftIndex] <= right[rightIndex]) {
                    mergedArr[i] = left[leftIndex++];
                } else {
                    mergedArr[i] = right[rightIndex++];
                }
            } else if (leftIndex >= left.length) { // 左子数组没有元素了
                mergedArr[i] = right[rightIndex++];
            } else {// 右子数组没有元素了
                mergedArr[i] = left[leftIndex++];
            }
        }
        return mergedArr;
    }


}
